package LCR剑指.LCR078;


import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int x,ListNode next){
        this.val = x;
        this.next = next;
    }
}

public class Solution {

    class PrioriEntity implements Comparable<PrioriEntity>{

        int val;
        ListNode ptr;

        public PrioriEntity() {}

        public PrioriEntity(int val, ListNode ptr) {
            this.val = val;
            this.ptr = ptr;
        }

        @Override
        public int compareTo(PrioriEntity o) {
            return this.val - o.val;
        }
    }

    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<PrioriEntity> pq = new PriorityQueue<PrioriEntity>();
        for (ListNode node : lists) {
            if(node!=null){
                pq.offer(new PrioriEntity(node.val, node));
            }
        }
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        //每次从pq中找出一个，然后判断其是否为null
        while (!pq.isEmpty()) {
            PrioriEntity p = pq.poll();
            if(p.ptr!=null){
                cur.next = p.ptr;
                cur = cur.next;
                if (p.ptr.next != null) {
                    pq.offer(new PrioriEntity(p.ptr.next.val, p.ptr.next));
                }
            }

        }
        return dummy.next;
    }

    public static void main(String[] args) {
        List<ListNode> lists = new ArrayList<ListNode>();
        lists.add(new ListNode(1,new ListNode(4,new ListNode(5,null))));
        lists.add(new ListNode(1,new ListNode(3,new ListNode(4,null))));
        lists.add(new ListNode(2,new ListNode(6,null)));
        Solution solution = new Solution();
        ListNode[] list = new ListNode[lists.size()];
        for(int i=0;i<lists.size();i++){
            list[i] = lists.get(i);
        }
        solution.mergeKLists(list);
    }
}